#include "heapSort.h"
#include<stdio.h>
#include<stdlib.h>
#include<time.h>


void heapSort(int a[], int n, float* tempo)
{
clock_t inicio, fim;
     inicio = clock();
     
   int i = n/2, pai, filho;
   int t;
 
   for (;;)
   {      
      if (i > 0)
      {
          i--;
          t = a[i];
      }
      else
      {
          n--;
          if (n == 0) {
             fim = clock();
             *tempo = ( (float)fim -(float)inicio ) / ( (float)CLOCKS_PER_SEC );
             printf("tempo heap=%f\n", *tempo ); // PENDENTE
             return;
          }     

          t = a[n];
          a[n] = a[0];
      }
     
      pai = i;
      filho = i*2 + 1;
 
      while (filho < n)
      {

          if ((filho + 1 < n)  &&  (a[filho + 1] > a[filho])){
              filho++;
              
          }

          if (a[filho] > t)
          {            
             a[pai] = a[filho];
             pai = filho;
             filho = pai*2 + 1;

          }
          else {
             break;
          }
      }
      a[pai] = t;

   }
   

}
